//
// Created by wlk12 on 2025/7/5.
//

// https://www.cnblogs.com/gaochundong/p/lock_free_programming.html


#include <iostream>
#include <atomic>
#include <thread>
#include <mutex>
#include <barrier>


class Stack
{
public:


    struct Node
    {
        int data{};
        std::atomic<Node*> next{};
    };


    Stack() = default;
    ~Stack()
    {
        while (this->top != nullptr)
        {
            auto tmp = this->top.load();
            this->top = this->top.load()->next.load();
            delete tmp;
        }
    }

    bool isEmpty()
    {
        return this->top == nullptr;
    }

    void push(int data)
    {
        auto* newNode = new Node{data};
        Node* old = nullptr;
        do
        {
            old = this->top.load();
            newNode->next = old;
        } while (!this->top.compare_exchange_weak(old, newNode));
    }

    int pop()
    {
        Node* tmp = nullptr;
        Node* newTop = nullptr;

        do
        {
            tmp = this->top.load();
            if (tmp == nullptr)
            {
                return -1;
            }
            newTop = tmp->next.load();
        } while (!this->top.compare_exchange_weak(tmp, newTop));

        int data = tmp->data;
        delete tmp;
        return data;
    }

private:
    std::atomic<Node*> top{};
};



int main()
{
    Stack stack;

    constexpr int pushCount = 10000;
    std::thread threads[10];
    std::barrier sync_point(std::size(threads));

    for (auto & t : threads)
    {
        t = std::thread([&](){
            sync_point.arrive_and_wait();
            for (int j = 0; j < pushCount; ++j)
            {
                stack.push(1);
            }
        });
    }

    for (auto& thread : threads)
    {
        thread.join();
    }

    std::atomic<int> count = 0;

    // while (!stack.isEmpty())
    // {
    //     stack.pop();
    //     count.fetch_add(1);
    // }

    std::barrier sync_point2(std::size(threads));
    for (auto & i : threads)
    {
        i = std::thread([&](){
            sync_point2.arrive_and_wait();
            for (int j = 0; j < pushCount; ++j)
            {
                if (!stack.isEmpty())
                {
                    stack.pop();
                    count.fetch_add(1);
                }
            }
        });
    }

    for (auto & thread : threads)
    {
        thread.join();
    }

    std::cout << "except: " << std::size(threads) * pushCount << ",  count:" << count << std::endl;

    return 0;
}

